package leetcode_top;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

import org.junit.*;

public class Ex315 {
    class Solution {
        public List<Integer> countSmaller(int[] nums) {
            int len = nums.length;
            if (len == 0) return new ArrayList<>();
            int[] idx = Stream.iterate(0, i -> i + 1).limit(len).mapToInt(Integer::valueOf).toArray();
            int[] res = new int[len];
            mergeSort(res, idx, nums, 0, len - 1);
            System.out.println(Arrays.toString(idx));
            return Arrays.stream(res).boxed().collect(Collectors.toList());
        }

        public void mergeSort(int[] res, int[] idx, int[] nums, int lo, int hi) {
            if (lo >= hi) return;
            int mid = (hi - lo) / 2 + lo;
            mergeSort(res, idx, nums, lo, mid);
            mergeSort(res, idx, nums, mid + 1, hi);
            if (nums[idx[mid]] <= nums[idx[mid + 1]]) return;
            merge(res, idx, nums, lo, mid, hi);
        }



        public void merge(int[] res, int[] idx, int[] nums, int lo, int mid, int hi) {
            int i = lo, j = mid + 1;
            int[] temp = new int[hi - lo + 1];
            int k = 0;
            //只有动左指针时才需要计算逆序对，增加的幅度为右指针偏移的数量
            while (i <= mid && j <= hi) {
                if (nums[idx[i]] <= nums[idx[j]]) {
                    res[idx[i]] += (j - mid - 1);
                    temp[k++] = idx[i++];
                } else {
                    temp[k++] = idx[j++];
                }
            }
            while (i <= mid) {
                res[idx[i]] += (j - mid - 1);
                temp[k++] = idx[i++];
            }
            while (j <= hi) {
                temp[k++] = idx[j++];
            }
            k = 0;
            for (int l = lo; l <= hi; l++) {
                idx[l] = temp[k++];
            }
        } 
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{5,2,6,1};
        System.out.println(s.countSmaller(nums));
    }
}
